package LeetCode;

import java.util.ArrayList;
import java.util.List;

public class LC_241_DifferentWaystoAddParentheses {

    public static void main(String[] args) {

    }

    static class Solution {
        List<Integer> diffWaysToCompute(String input) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < input.length(); i++) {
                char c = input.charAt(i);
                if ('+' == c || '-' == c || '*' == c) {
                    String lv = input.substring(0, i);
                    String rv = input.substring(i + 1);
                    List<Integer> lefts = diffWaysToCompute(lv);
                    List<Integer> rights = diffWaysToCompute(rv);
                    for (int j : lefts) {
                        for (int k : rights) {
                            int temp = 0;
                            switch (c) {
                                case '+':
                                    temp = j + k;
                                    break;
                                case '-':
                                    temp = j - k;
                                    break;
                                case '*':
                                    temp = j * k;
                            }
                            res.add(temp);
                        }
                    }
                }
            }
            if (res.isEmpty()) res.add(Integer.valueOf(input));
            return res;
        }
    }

}